#include <iostream>
#include <vector>
using namespace std;

/*
 * 简单的岛屿，之前做过复习一遍了
 * */

//dfs
class Solution {
public:

    const int dx[4] = {1, 0, 0, -1};
    const int dy[4] = {0, 1, -1, 0};

    int dfs(vector<vector<int>>& grid, int sr, int sc) {
        auto n = grid.size(), m = grid[0].size();
        if (sr < 0 || sr >= n || sc < 0 || sc >= m || grid[sr][sc] != 1) {
            return 0;
        }

        grid[sr][sc] = 0;
        int ans = 1;
        for (int i = 0; i < 4; ++i) {
            int mx = sr + dx[i], my = sc + dy[i];
            ans += dfs(grid, mx, my);
        }
        return ans;
    }

    int maxAreaOfIsland(vector<vector<int>>& grid) {
        if (grid.empty()) {
            return 0;
        }

        int res = 0;
        auto n = grid.size(), m = grid[0].size();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                res = max(res, dfs(grid, i, j));
            }
        }
        return res;
    }
};


int main() {

    vector <vector<int>> grid = {{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
                                 {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                                 {0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
                                 {0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0},
                                 {0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0},
                                 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
                                 {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                                 {0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}};
    Solution solution;
    auto result = solution.maxAreaOfIsland(grid);
    cout << result << endl;
    return 0;
}